# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 4_binary_heap.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2021/12/24 16:05
------------------------------------------
    二叉堆的相关代码，本文件中的代码均是为了构建小根堆
    Tips:
        注意，up/down_adjust中，连续交换节点部分进行了优化。
        并不一定真的要交换，只需要把交换一方的值存入temp变量，做单向覆盖，
        循环结束后，再把temp的值存入交换后的最终位置即可
"""


def up_adjust(array):
    """
        二叉堆的尾节点上浮，小根堆
    """
    child_index = len(array) - 1
    parent_index = (child_index - 1) // 2

    # temp，保存插入的叶子节点值，用于最后的赋值
    temp = array[child_index]

    while child_index > 0 and temp < array[parent_index]:
        # 无需真正交换，单向赋值即可
        array[child_index] = array[parent_index]
        child_index = parent_index
        parent_index = (parent_index - 1) // 2

    array[child_index] = temp


def down_adjust(parent_index, length, array):
    """
        二叉堆节点下沉
        :param parent_index: 待下沉的节点坐标
        :param length: 堆的长度范围
        :param array: 原数组
    """

    # temp，保存父节点的值，用于最后赋值
    temp = array[parent_index]

    # 这里默认用了左孩子的索引计算，为什么没有右孩子的节点计算？别急,这里写哪个都行，后边进行了处理。
    child_index = 2 * parent_index + 1

    while child_index < length:
        # 如果有右孩子，且右孩子的值小于左孩子的值，则定位到右孩子(找出最小的孩子)
        if child_index + 1 < length and array[child_index + 1] < array[child_index]:
            child_index += 1

        # 如果父节点的值小于任何一个孩子的值，则跳出
        if temp < array[child_index]:
            break

        # 无需正交换，单向赋值即可
        array[parent_index] = array[child_index]
        parent_index = child_index
        child_index = 2 * child_index + 1

    array[parent_index] = temp


def build_heap(array):
    """
        构建二叉堆，小根堆
        :param array: 原数组
    """
    # 从最后一个非叶子节点依次下沉
    # len(array) - 1 是最后一个节点的索引，肯定为叶子节点。而堆下沉找的非叶子结点，即它的父节点。
    # 而从子节点索引计算父节点索引的通用公式为 (child_index - 1) // 2,
    # 即 (len(array) - 1 - 1) // 2,即 len(array) - 2)

    array_len = len(array)
    for i in range((len(array) - 2) // 2, -1, -1):
        down_adjust(i, array_len, array)


def demo():
    my_array = [1, 3, 2, 6, 5, 7, 8, 9, 10, 0]
    print(f"src:\t {my_array}")
    up_adjust(my_array)
    print(f"up:\t\t {my_array}")
    print('-' * 50)

    my_array2 = [7, 1, 3, 10, 5, 2, 8, 9, 6]
    print(f"src:\t {my_array2}")
    build_heap(my_array2)
    print(f"build:\t {my_array2}")


if __name__ == '__main__':
    demo()
